<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>双向链表</title>
</head>
<body>
<script>
    // 创建双向链表的构造函数
    function DoublyLinkedList(){
        // 创建节点构造函数
        function Node (element){
            this.element = element
            this.next = null
            this.prev = null // 新添加的用于指向上一个节点
        }
        // 定义属性
        this.length = 0
        this.head = null
        this.tail = null // 新添加的用于指向链表末尾的节点
        
        /*双向链表的相关方法*/

        // 在尾部追加数据
        DoublyLinkedList.prototype.append = function (element){
            // 根据元素创建节点
            var newNode = new Node(element)
            // 判断列表是否为空列表
            if(this.head ===null){
                this.head = newNode // 头部 也是链表
                this.tail = newNode // 尾部 只是用来记录每一次的尾部的
            }else{
                this.tail.next = newNode // 让原先的尾部的next为当前加入的节点
                newNode.prev = this.tail // 让当前加入的节点的上一个指向为原先的尾部
                this.tail = newNode // 尾部为当前加入的节点
            }
            this.length++
        }

        // 正向遍历
        DoublyLinkedList.prototype.forwardString = function (){
            var current = this.head
            var forwarStr = ""
            while (current){
                forwarStr+= "," + current.element
                current  =current.next
            }
            return forwarStr.slice(1)
        }
        // 反向遍历
        DoublyLinkedList.prototype.reverseString = function(){
            var current = this.tail
            var reverseStr = ""
            while(current){
                reverseStr+= "," + current.element
                current = current.prev
            }
            return reverseStr.slice(1)
        }
        // 实现toString方法
        DoublyLinkedList.prototype.toString = function (){
            return this.forwardString()
        }

        // 任意位置插入
        DoublyLinkedList.prototype.insert = function (position,element){
            // 判断是否越界
            if(position<0||position>this.length)return false
            // 创建新节点
            var newNode = new Node(element)
            // 判断插入的位置
            if(position===0){ // 在第一个位置插入
                // 判断链表是否为空
                if(this.head === null){
                    this.head = newNode
                    this.tail = newNode
                }else{
                    this.head.prev = newNode // 将头部的上一个节点指向为新加入的节点
                    newNode.next = this.head // 新节点的下一个节点指向为头节点
                    this.head = newNode // 头部节点变为新节点
                }
            }else if(position===this.length){ // 插入到最后的情况
                this.tail.next = newNode
                newNode.prev = this.tail
                this.tail = newNode
            }else{ // 在中间任意位置插入
                // 定义属性
                var index  = 0
                var current = this.head
                var previous = null
                // 查找到正确的位置
                while(index++ < position){
                    previous = current // 存储当前节点
                    current = current.next // 存储下一节点
                }
                // 交换节点的指向顺序
                newNode.next = current
                newNode.prev = previous
                current.prev = newNode
                previous.next = newNode
            }
            this.length++
            return true
        }

        // 根据下标移除数据
        DoublyLinkedList.prototype.removeAt = function (position){
            // 判断越界问题
            if(position<0 || position>this.length) return null
            // 2. 判断移除的位置
            var current = this.head
            if(position===0){
                if(this.length===1){
                    this.head = null
                    this.tail = null
                }else{
                    this.head = this.head.next
                    this.head.prev = null
                }
            }else if(position === this.length-1){
                current = this.tail // 不知道这个变量的作用是什么
                this.tail = this.tail.prev
                this.tail.next = null 
            }else{
                var index = 0
                var previous = null
                while(index++ <position){ // 这里找到的是移除节点的位置的上一个节点
                    previous = current // 存储当前节点
                    current = current.next // 存储移除数据的下标的next
                }
                previous.next = current.next // 删除的下标的前一个元素的next指向删除的下标的前一个元素的next的next
                current.next.prev = previous // 删除元素的下标的下一个元素的prev指向删除的下标的前一个元素
            }
            this.length--
            return current.element
        }

        // 根据元素获取在链表中的位置
        DoublyLinkedList.prototype.indexOf = function(element){
            // 保存信息
            var current =  this.head 
            var index = 0
            // 查找正确的信息
            while(current){
                if(current.element===element){
                    return index
                }
                index++
                current = current.next
            }
            // 运行到这里说明没有找到
            return -1
        }

        // 根据元素删除
        DoublyLinkedList.prototype.remove = function(element){
            var index = this.indexOf(element)
            return this.removeAt(index)
        }

        // 判断是否为空
        DoublyLinkedList.prototype.isEmpty = function(){
            return this.length === 0
        }

        // 获取链表长度
        DoublyLinkedList.prototype.size = function(){
            return this.length
        }

        // 获取第一个元素
        DoublyLinkedList.prototype.getHead = function(){
            return this.head.element
        }

        // 获取最后一个元素
        DoublyLinkedList.prototype.getTail = function(){
            return this.tail.element
        }
        
    }
    
    // 创建双向链表对象
    var list = new DoublyLinkedList()

    // 追加元素
    list.append("abc")
    list.append("cba")
    list.append("nba")
    list.append("mba")

    // 遍历所有的结果
    alert(list.forwardString()) // abc cba nba mba
    alert(list.reverseString()) // mba nba cba abc
    alert(list.toString()) // abc cba nba mba
    // insert 方法测试
    list.insert(0,"100")
    list.insert(2,"200")
    list.insert(6,"300")
    alert(list) // 100 abc 200 cba nba mba 300
    // removeAt方法
    alert(list.removeAt(0)) // 100
    alert(list.removeAt(1)) // 200
    alert(list.removeAt(4)) // 300
    alert(list) // abc cba nba mba 
    // indexOf方法
    alert(list.indexOf("abc")) // 0
    alert(list.indexOf("cba")) // 1
    alert(list.indexOf("mba")) // 3
    // remove方法测试
    alert(list.remove("abc")) // abc
    alert(list) // cba,nba,mba
    // 测试其他代码
    alert(list.getHead())
    alert(list.getTail())
    alert(list.isEmpty())
    alert(list.size())
</script>
</body>
</html>